<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 连接词 -->
    <script>
      var findAllConcatenatedWordsInADict = function (words) {
        // 典型的trie树，但是注意前缀可能存在备选单词的情况
        let trie = {}
        for (const word of words) {
          //  注意空字符串过滤
          if (!word) continue
          let root = trie
          for (const c of word) {
            if (!root[c]) root[c] = {}
            root = root[c]
          }
          root['is_word'] = true
        }
        let res = []
        for (const word of words) {
          if (dfs(word, trie, 0, 0)) {
            res.push(word)
          }
        }
        return res
        function dfs(word, curNode, cnt, idx) {
          // dfs停机条件
          if (idx === word.length) {
            if (cnt >= 1 && curNode['is_word']) return true
            return false
          }
          // 单词前缀遇到"is_word"键，则说明该前缀存在于列表中
          // 则cnt+1，同时idx不变是为了继续向后探索更长的前缀
          if (curNode['is_word']) {
            // 注意下面参数trie即从字典树头部开始接着idx遍历新的单词
            if (dfs(word, trie, cnt + 1, idx)) return true
          }
          // 单词某个字符在字典树当前节点不存在，则直接返回false
          if (!curNode[word[idx]]) return false
          // 正常递归字典树，索引增加
          if (dfs(word, curNode[word[idx]], cnt, idx + 1)) return true
          return false
        }
      }
      console.log(findAllConcatenatedWordsInADict(['cat', 'cats', 'catsdogcats', 'dog', 'dogcatsdog', 'hippopotamuses', 'rat', 'ratcatdogcat']))
    </script>
  </body>
</html>
